import java.util.Arrays;

public class Solution1478 {
    public int minDistance(int[] houses, int k) {
        Arrays.sort(houses);
        int[][] f=new int[houses.length][k+1];
        for (int i=1;i<houses.length;i++){
            for (int p=0;p<=i;p++){
                f[i][1]+=Math.abs(houses[p]-houses[i/2]);
            }
            for (int j=2;j<=Math.min(i+1,k);j++){
                f[i][j]=Integer.MAX_VALUE;
                for (int t=0;t<i;t++){
                    int temp=f[t][j-1];
                    for (int q=t+1;q<=i;q++){
                        temp+=Math.abs(houses[q]-houses[(i+t+1)/2]);
                    }
                    f[i][j]=Math.min(f[i][j],temp);
                }
            }
        }
        return f[houses.length-1][k];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1478().minDistance(new int[]{1,4,6,7},1));
    }
}
